package 剑指专题.动态规划;


/*
 * Author：江松
 * Date：2023/3/21 18:57
 *
 *
 跳台阶扩展问题:
 fi为到i阶的走法
 有f(i)=f(i-1)+f(i-2)+...+f(1)
 f(i-1)=f(i-2)+...f(1)
 所以f(i)=2*f(i-1)
 */

public class Main4 {
    //只与上一个状态有关，可用常数优化
    public int jumpFloorII(int target) {
        int dp=1;
        for(int i=2;i<=target;++i){
            dp<<=1;
        }
        return dp;
    }
    /*
    public int jumpFloorII(int target) {
        int dp[]=new int[target];
        dp[1]=1;
        for(int i=2;i<=target;++i){
            dp[i]+=2*dp[i-1];
        }
        return dp[target];
    }
    */
}
